package binarysearch.test34;

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 *
 * @author code_yc
 * @version 1.0
 * @date 2020/7/11 10:11
 */
public class Solution1 {

    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        int l = 0;
        int r = nums.length - 1;
        // 首先找左边界
        while (l < r) {
            int m = l + ((r - l) >> 1);
            if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        int left = nums[l] == target ? l : -1;
        l = 0;
        r = nums.length - 1;
        // 寻找右边界
        while (l < r) {
            int m = l + ((r - l + 1) >> 1);
            if (nums[m] > target) {
                r = m - 1;
            } else {
                l = m;
            }
        }
        int right = nums[l] == target ? l : -1;
        return new int[]{left, right};
    }
}
